1. Field of the Invention
The present invention relates to digital signal processing, and more specifically, to a programmable digital finite impulse response (FIR) filter.
2. Description of the Prior Art
Finite impulse response (FIR) filters are important components in digital communications systems. Much effort has been made to improve filter performance, reduce hardware, and increase operating speed. In addition, software radios, such as those introduced in J. Mitola, “The Software Radio Architecture,” IEEE Communications Magazine, vol. 33, pp. 26-38, May 1995 or E. Buracchini, “The Software Radio Concept,” IEEE Communications Magazine, vol. 38, pp. 138-143, September 2000, have recently gained much attention due to the need for integrated and reconfigurable communications systems. To this end, reconfigurability has become an important issue for future filter design.
FIR filters can be used to perform a wide variety of tasks such as spectral shaping, matched filtering, noise rejection, channel equalization, etc. Hence, various architectures and implementation methods have been proposed to improve the performance of filters with respect to speed and complexity. However, due to the recent explosive proliferation in wired and wireless communication standards, traditional hardwired devices may be less suitable for future communication needs.
On the other hand, software radio has gained much attention from researchers worldwide due to a strong demand for reconfigurable communication systems capable of performing multi-standard operations. In light of this trend, programmability and reconfigurability need be taken into account in filter architecture design.
A typical N-tap FIR filter can be described by:
                              y          ⁡                      [            n            ]                          =                              ∑                          i              =              0                                      N              -              1                                ⁢                                    h              i                        ·                          x              ⁡                              [                                  n                  -                  i                                ]                                                                        (                  Eqn          .                                          ⁢          1                )            
where,
y[n] is a filtered digital signal, n being an index of elements of the signal;
hi is a filtering coefficient; and
x is an unfiltered digital signal.
It is well known in the art that a canonical signed digit (CSD) representation can be used to reduce the complexity of a digital FIR filter implementation as in R. M. Hewlitt and E. S. Swartzlantler Jr., “Canonical Signed Digit Representation for FIR Digital Filters,” in Proc. of IEEE Workshop on Signal Processing Systems, 2000, pp.416-426; M. Tamada and A. Nishihara, “High-Speed FIR Digital Filter with CSD Coefficients Implemented on FPGA,” in Proc. of the ASP-DAC, 2001, pp. 7-8; and Y. M. Hasan, L. J. Karem, M. Falkinburg, A. Helwig, and M. Ronning, “Canonic Signed Digit Chebyshev FIR Filter Design,” IEEE Signal Processing Letters, vol. 8, pp. 167-169, June 2001, for example. Encoding filter coefficients using a CSD representation reduces the number of partial products and thus saves silicon area and power consumption in hardware implementation. Hence, this technique has been popular for fixed-coefficient implementation of FIR filters. According to the CSD representation:
                              h          i                =                              ∑                          k              =              0                                                      M                i                            -              1                                ⁢                                    d                              i                ,                k                                      ·                          2                              -                                  p                  k                                                                                        (                  Eqn          .                                          ⁢          2                )                                          and          ⁢                                          ⁢          thus                ,                                                                      y          ⁡                      [            n            ]                          =                              ∑                          i              =              0                                      N              -              1                                ⁢                                    ∑                              k                =                0                                                              M                  i                                -                1                                      ⁢                                          d                                  i                  ,                  k                                            ·                              2                                  -                                      p                    k                                                              ·                              x                ⁡                                  [                                      n                    -                    i                                    ]                                                                                        (                  Eqn          .                                          ⁢          3                )            
where,
di,k is an element of the set {1, 0, −1};
pk is an element of the set {0, . . . , L}, where L+1 is the length of the coefficients;
and
Mi is the number of nonzero digits in hi.
When applying the CSD representation to implementing programmable, rather than fixed-coefficient, FIR filters, it is only natural to implement the same number of programmable CSDs for each filter coefficient to maintain regularity. However, for most filters, only a few taps require high-precision coefficients. Valuable hardware resources will be wasted if all taps are implemented with the highest precision. To minimize hardware complexity, programmable FIR filters restricting the number of allowable nonzero CSDs in every tap have been proposed in T. Zhangwen, Z. Zhanpeng, Z. Jie, and M. Hao, “A High-Speed, Programmable, CSD Coefficient FIR Filter,” in Proc. of 4th International Conference on ASIC, 2001, pp.397-400; and in K. T. Hong, S. D. Yi, and K. M. Chung, “A High-Speed Programmable FIR Digital Filter Using Switching Arrays,” in Proc. of IEEE Asia Pacific Conference on Circuits and Systems, 1996, pp. 492-495. Unfortunately, this restriction may lower the coefficient precision and degrade the frequency response of the filter, and it may also induce a large overhead by assigning more CSDs than necessary to most taps. Another hardware-efficient implementation of programmable FIR filters with CSD coefficients has been presented in K. Y. Khoo, A. Kwentus, and A. N. Willson Jr., “A Programmable FIR Digital Filter Using CSD Coefficients,” IEEE Journal of Solid-State Circuits, vol. 31, pp. 869-874, June 1996. This implementation includes a 32-tap linear-phase filter with two nonzero CSDs in each tap. Additional nonzero CSDs can be allocated to specific filter taps, making it a reconfigurable FIR filter architecture. Nevertheless, some computational resources can still be unused and the critical path can be quite longin some cases.
Another state of the art programmable FIR filter is taught by Willson, Jr. et al. in U.S. Pat. No. 5,479,363, which is included herein by reference. Consider FIG. 1 showing taps of a filter of a kind taught in U.S. Pat. No. 5,479,363. The filter comprises a series of p-taps 70a-f that include tap coefficient multipliers 74a-f, adders 78a-f, unit delays (registers) 77a-f, and delay bypass lines 75a-f for filtering digital data on a line 72. Assuming each of the p-taps 70a-f has a two-digit signed coefficient multiplier, bypass lines 77a-f can be selectively connected to bypass specific unit delays, merging p-taps to effectively increase the precision of the coefficient multipliers. This is shown in FIG. 1, where bypass line 75b is active and bypasses the corresponding register 77b such that a four-digit coefficient is realized by multipliers 74b, 74c and adders 78b, 78c. A six-digit coefficient is realized in a similar way. A fundamental shortcoming of the filter of FIG. 1 is that the critical path depends on coefficient precision. In the four-digit coefficient, for example, the critical path includes the multiplier 74b and the two adders 78b, 78c, while the six-digit coefficient has a longer critical path including a multiplier and three adders. This dependence of critical path on precision results in slow, inefficient, and somewhat unpredictable performance.
Generally, the prior art programmable FIR filters suffer from drawbacks of program inflexibility, speed, precision range, and critical path dependence on precision.